#include<iostream>
template <typename Comparable>
  class BinarySearchTree
  {
  public:
  BinarySearchTree( );
  BinarySearchTree( const BinarySearchTree & rhs );
  BinarySearchTree( BinarySearchTree && rhs );
  ~BinarySearchTree( );
 
   const Comparable & findMin( ) const;
   const Comparable & findMax( ) const;
   bool contains( const Comparable & x ) const;
   bool isEmpty( ) const;
   void printTree( ostream & out = cout ) const;
  
   void makeEmpty( );
   void insert( const Comparable & x );
   void insert( Comparable && x );
   void remove( const Comparable & x );
  
   BinarySearchTree & operator=( const BinarySearchTree & rhs );
   BinarySearchTree & operator=( BinarySearchTree && rhs );
  
   private:
   struct BinaryNode
   {
   Comparable element;
   BinaryNode *left;
   BinaryNode *right;
  
   BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
   : element{ theElement }, left{ lt }, right{ rt } { }
  
   BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
   : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
   };
  
   BinaryNode *root;
  
   void insert( const Comparable & x, BinaryNode * & t );
   void insert( Comparable && x, BinaryNode * & t );
   void remove( const Comparable & x, BinaryNode * & t );
   BinaryNode * findMin( BinaryNode *t ) const;
   BinaryNode * findMax( BinaryNode *t ) const;
   bool contains( const Comparable & x, BinaryNode *t ) const;
   void makeEmpty( BinaryNode * & t );
   void printTree( BinaryNode *t, ostream & out ) const;
   BinaryNode * clone( BinaryNode *t ) const;
 };
   bool contains( const Comparable & x ) const
   {
   return contains( x, root );
   }
   void insert( const Comparable & x )
   {
   insert( x, root );
   }
   void remove( const Comparable & x )
   {
   remove( x, root );
   }
   bool contains( const Comparable & x, BinaryNode *t ) const
   {
     if( t == nullptr )
        return false;
     else if( x < t->element )
        return contains( x, t->left );
     else if( t->element < x )
        return contains( x, t->right );
     else
        return true; 
   }
template <typename Object, typename Comparator=less<Object>>
class BinarySearchTree
  {
  public:
   
   BinarySearchTree( );
   BinarySearchTree( const BinarySearchTree & rhs );
   BinarySearchTree( BinarySearchTree && rhs );
   ~BinarySearchTree( );
 
   const Object & findMin( ) const;
   const Object & findMax( ) const;
   bool contains( const Object & x ) const;
   bool isEmpty( ) const;
   void printTree( ostream & out = cout ) const;
  
   void makeEmpty( );
   void insert( const Object & x );
   void insert( Object && x );
   void remove( const Object & x );
  
   BinarySearchTree & operator=( const BinarySearchTree & rhs );
   BinarySearchTree & operator=( BinarySearchTree && rhs );
 
  private:
 
   BinaryNode *root;
   Comparator isLessThan;

13 struct BinaryNode
   {
   Object element;
   BinaryNode *left;
   BinaryNode *right;
  
   BinaryNode( const Object & theElement, BinaryNode *lt, BinaryNode *rt )
   : element{ theElement }, left{ lt }, right{ rt } { }
  
   BinaryNode( Object && theElement, BinaryNode *lt, BinaryNode *rt )
   : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
   };
  
   BinaryNode *root;
  
   void insert( const Object & x, BinaryNode * & t );
   void insert( Object && x, BinaryNode * & t );
   void remove( const Object & x, BinaryNode * & t );
   BinaryNode * findMin( BinaryNode *t ) const;
   BinaryNode * findMax( BinaryNode *t ) const;
   bool contains( const Object & x, BinaryNode *t ) const;
   void makeEmpty( BinaryNode * & t );
   void printTree( BinaryNode *t, ostream & out ) const;
   BinaryNode * clone( BinaryNode *t ) const;

   bool contains( const Object & x, BinaryNode *t ) const
   {
      if( t == nullptr )
        return false;
      else if( isLessThan( x, t->element ) )
        return contains( x, t->left );
      else if( isLessThan( t->element, x ) )
        return contains( x, t->right );
      else
        return true; 
   }
};
   BinaryNode * findMin( BinaryNode *t ) const
   {
   if( t == nullptr )
      return nullptr;
   if( t->left == nullptr )
      return t;
   return findMin( t->left );
   }
   BinaryNode * findMax( BinaryNode *t ) const
   {
   if( t != nullptr )
       while( t->right != nullptr )
           t = t->right;
   return t;
   }
   void insert( const Comparable & x, BinaryNode *&t)
   {
   if( t == nullptr )
   t = new BinaryNode{ x, nullptr, nullptr };
   else if( x < t->element )
   insert( x, t->left );
   else if( t->element < x )
   insert( x, t->right );
   else
   ; 
   }
   void insert( Comparable && x, BinaryNode *&t)
   {
   if( t == nullptr )
       t = new BinaryNode{ std::move( x ), nullptr, nullptr };
   else if( x < t->element )
       insert( std::move( x ), t->left );
   else if( t->element < x )
       insert( std::move( x ), t->right );
   else
   ; 
   }
   void remove( const Comparable & x, BinaryNode *&t)
   {
      if( t == nullptr )
         return; // Item not found; do nothing
      if( x < t->element )
         remove( x, t->left );
      else if( t->element < x )
         remove( x, t->right );
      else if( t->left != nullptr && t->right != nullptr ) // Two children
      {
         t->element = findMin( t->right )->element;
         remove( t->element, t->right );
      }
      else
      {
         BinaryNode *oldNode = t;
         t = ( t->left != nullptr ) ? t->left : t->right;
         delete oldNode;
      }
   }
   ~BinarySearchTree( )
   {
       makeEmpty( );
   }
   void makeEmpty( BinaryNode * & t )
   {
       if( t != nullptr )
       {
           makeEmpty( t->left );
           makeEmpty( t->right );
           delete t;
       }
       t = nullptr;
   }
   BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
   {
       root = clone( rhs.root );
   }
   BinaryNode * clone( BinaryNode *t ) const
   {
       if( t == nullptr )
           return nullptr;
       else
           return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
   }
